#include<vector>
#include<iostream>
using namespace std;

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        // 每个位置的蓄水量=min(左边最大值, 右边最大值) - height[i]
        vector<int> l(n), r(n);
        l[0] = 0, r[n - 1] = 0;

        for (int i = 1; i < n; i ++) {
            l[i] = max(height[i - 1], l[i - 1]);
            r[n - i - 1] = max(height[n - i], r[n - i]); 
        }

        int res = 0, cur_height = 0;
        for (int i = 0; i < n; i++) {
            cur_height = max(0, min(l[i], r[i]) - height[i]);
            res += cur_height;
        }
        cout << endl;

        return res;
    }
};